package com.scqzy.shengchunqiang.sword2offer.day15;

import java.util.*;

/**
 * @Description: 剑指 Offer 36. 二叉搜索树与双向链表
 * @Author 盛春强
 * @Date 2021/8/23 0:21
 */
public class TreeToDoublyList {

    public Node treeToDoublyList(Node root) {
        if (Objects.isNull(root)) {
            return null;
        }
        List<Node> list = new ArrayList<>();
        Deque<Node> deque = new ArrayDeque<>();
        Node node = root;
        while (Objects.nonNull(node) || !deque.isEmpty()) {
            while (Objects.nonNull(node)) {
                deque.push(node);
                node = node.left;
            }
            list.add(deque.peek());
            node = deque.pop().right;
        }
        for (int i = 0; i < list.size() - 1; i++) {
            list.get(i).right = list.get(i + 1);
            list.get(i + 1).left = list.get(i);
        }
        list.get(list.size() - 1).right = list.get(0);
        list.get(0).left = list.get(list.size() - 1);
        return list.get(0);
    }

    Node pre;
    Node head;

    public Node treeToDoublyList1(Node root) {
        if (Objects.isNull(root)) {
            return null;
        }
        dfs(root);
        head.left = pre;
        pre.right = head;
        return head;
    }

    private void dfs(Node node) {
        if (Objects.isNull(node)) {
            return;
        }
        dfs(node.left);
        if (Objects.isNull(head)) {
            head = node;
            // pre = node;
        }
        if (Objects.nonNull(pre)) {
            pre.right = node;
            node.left = pre;
        }
        pre = node;
        dfs(node.right);
    }

    class Node {
        public int val;
        public Node left;
        public Node right;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _left, Node _right) {
            val = _val;
            left = _left;
            right = _right;
        }
    }

    ;
}
